package 数据结构.LinkList.diamond;


//题目：LeetCode24 交换链表
// 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
// 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
//输入：head = [1,2,3,4]
//输出：[2,1,4,3]


import javax.swing.*;
//todo：总结
/*
* todo：总结：
* 虚拟头节点：
* 利用虚拟头节点记录头指针【虚拟头节点：无实际意义，主要作用是
   tip:1.dummy.next=head
      2.利用临时存储dummy【其实这里就是不让dummy去改变，所以用临时的prev记录他的位置然后去变化
         ListNode prev=dummy
      3.利用head去移动【因为dummy已经记录了head，所以dummy不能移动，但此时的head就可以随便搞了】
      4.这里的dummy也不能随便移动，因为要靠dummy.next去得到头节点
* 1.a=pre.next.next.val;
    pre.next = head;
    b=pre.next.next.val;
    在这里中：pre.next.next=head.next
    * 【因为前面前面pre.next=head 了，所以这里的per.next.next不是原来的的了，a!=b】
* 2.如果没有head=prev.next的情况，那么节点本地的vale是不会变的，但他的next
    * 会因为head.next=prev 此时：head：val：不变，仍是1 next：变了
  3.如何移动节点：
  *         prev=xxx
            prev=head;
            head=head.next;这样子就可以实现移动了
         那些prev.next=xx都不是移动，是对该节点的下一个节点进行设置而已
   4.head.next.next:解读：
   如果出现head.next.next：拆开解读：head.next 看成一个节点 a
    然后再.next的话其实就是设置节点a的下一个节点是什么 【是head】，
    即a.next=head，将a的下一个节点指向head
    如head.next就是设置head的下一节点
    设置了head.next.next之后，如果再设置head.next 那么关系会断开【因为节点变了】
    5.在刚开始缓存节点的作用：
    *     1---2---3---4
    *    后面因为head.next被改变了，所以head.next.next的就不是原来的了
    *       所以如果后面要用到，得先ListNode tem=head.next.next【
    *           作用：得到了原先的节点的所有信息 val ：3 next：4
    *          【这样子其实也得到了后面的链表，因为是牵连着的，
    *               只有前一个节点知道后一个节点的信息】
* */
public class exchange {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        head.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        swapPairs(head);
    }

    private static void printListNode(ListNode head) {
        ListNode tem = head;
        while (tem != null) {
            System.out.print(tem.val + "--->");
            tem = tem.next;
        }
    }


    /*1.pre.next.next.val;
    pre.next = head;
    pre.next.next.val;//
    在这里中：pre.next.next=head.next【因为前面
    前面pre.next=head 了，所以这里的per.next.next不是原来的的了】*/
    /*2.如果没有head=prev.next的情况，那么节点本地的vale是不会变的，但他的next
     * 会因为head.next=prev 此时：head：val：不变，仍是1 next：变了
     * */
    public static ListNode swapPairs2(ListNode head) {
        //利用虚拟头节点记录头指针【虚拟头节点：无实际意义，主要作用是
        //tip:1.dummy.next=head
        //      2.利用临时存储dummy【其实这里就是不让dummy去改变，所以用临时的prev记录他的位置然后去变化
        //      3.利用head去移动【因为dummy已经记录了head，所以dummy不能移动，但此时的head就可以随便搞了】
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode prev = dummyNode; //prev 0
        //有了虚拟头节点之后呢，就可以让头节点去随便移动了【不用再创建一个临时的去存储head】
        //那如何找头节点：虚拟头节点的下一个就是了头节点了
        //然后就可以利用头节点的移动变化去操作了
        while (prev.next != null && prev.next.next != null) {
            //0--1--2--3--4
/*            dummy.next=pre;
            pre.next=front;
            tem=front.next.next;
            front.next=tem;
            front=tem;
            pre=pre.next.next;*/
            ListNode temp = head.next.next; // 缓存 next tem =3
            System.out.println(temp.val);
            prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
            //prev.next =had.next=1.next=2
            head.next.next = head;// 将 head.next(prev.next) 的next，指向 head
            //head.next 是2  然后head.next.next=head是表示2-->1
            //head 1 head.next 2   head.next.next=2.next=head =1
            //解读：如果出现head.next.next：拆开解读：head.next 看成一个节点 a
            //关键     然后再.next的话其实就是设置节点a的下一个节点是什么 【是head】，
            //     即a.next=head，将a的下一个节点指向head
            //如head.next就是设置head的下一节点
            //设置了head.next.next之后，如果再设置head.next 那么关系会断开【因为节点变了】
            head.next = temp;               // 将head 的 next 接上缓存的temp
            //即head-->tmp
//            System.out.println(head.val);
            prev = head;                    // 步进1位
            System.out.println("pr" + prev.val);
            System.out.println("p.ne" + prev.next.val);
            head = head.next;               // 步进1位
//            System.out.println(head.val);
            //如何没有让head=某个节点，那么无论head的next怎么变，head的val都不会变
            //所以的话如果将最后将prev=head：那么就是prev 的val和next都是head的了
//            System.out.println(head.val);
        }
        printListNode(dummyNode.next);
        return null;
    }

    /*    ListNode pre=head.next;
        pre.next.next.val;
        pre.next = head;
        pre.next.next.val;//在这里中：pre.next.next=head.next【因为卡前面
        //前面pre.next=head 了，所以这里的per.next.next不是原来的的了】*/
    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        //这里的判断条件：根据那个移动的来，记得如果有用到next。next记得要两个判断
        while (prev.next != null && prev.next.next != null) {
            ListNode tem = head.next.next;
            prev.next = head.next;
            ListNode head2=head;
            head.next.next=head;

//            head.next.next = head;
            //因为这里要去指向原来的head.next.next，但后来的
            //这个已经不是原来的了 所以上面得去记录tem
            head.next = tem;
            //节点的移动：prev=xxx
            prev = head;
            head = head.next;
        }
        printListNode(dummy.next);
        return dummy.next;
    }
}
